{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Beautiful Integers in the Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfBeautifulIntegers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #范围中美丽整数的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你正整数&nbsp;<code>low</code>&nbsp;，<code>high</code>&nbsp;和&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个数满足以下两个条件，那么它是 <strong>美丽的</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>偶数数位的数目与奇数数位的数目相同。</li>\n",
    "\t<li>这个整数可以被&nbsp;<code>k</code>&nbsp;整除。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回范围&nbsp;<code>[low, high]</code>&nbsp;中美丽整数的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>low = 10, high = 20, k = 3\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>给定范围中有 2 个美丽数字：[12,18]\n",
    "- 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。\n",
    "- 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。\n",
    "以下是一些不是美丽整数的例子：\n",
    "- 16 不是美丽整数，因为它不能被 k = 3 整除。\n",
    "- 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。\n",
    "给定范围内总共有 2 个美丽整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>low = 1, high = 10, k = 1\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>给定范围中有 1 个美丽数字：[10]\n",
    "- 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。\n",
    "给定范围内总共有 1 个美丽整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>low = 5, high = 5, k = 2\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>给定范围中有 0 个美丽数字。\n",
    "- 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt; low &lt;= high &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt; k &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-beautiful-integers-in-the-range](https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-beautiful-integers-in-the-range](https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n20\\n3', '1\\n10\\n1', '5\\n5\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        # 位数小于等于5 直接暴力\n",
    "        def getResLT5(num):\n",
    "            res = 0\n",
    "            for num in range(0,num+1):\n",
    "                if num % k != 0:\n",
    "                    continue\n",
    "\n",
    "                a,b = 0,0\n",
    "                for w in str(num):\n",
    "                    if int(w) % 2 == 0:\n",
    "                        a += 1\n",
    "                    else:\n",
    "                        b += 1\n",
    "\n",
    "                if a == b:\n",
    "                    res += 1\n",
    "                    \n",
    "            return res\n",
    "        \n",
    "        def getRes(num):\n",
    "            s = str(num)\n",
    "            if len(s) <= 5:\n",
    "                return getResLT5(num)\n",
    "            \n",
    "            \n",
    "            l = (len(s) + 1) // 2\n",
    "            r = len(s) - l\n",
    "            \n",
    "            lnum = int(s[:l])\n",
    "            \n",
    "            # 10^t\n",
    "            ten = 10 ** r\n",
    "            \n",
    "            # 当 left ∈ [1,lnum) 时，right ∈ [0,10^t)\n",
    "            # 存储right\n",
    "            # key = (偶-奇，余数)\n",
    "            cnt = Counter()\n",
    "            \n",
    "            for num in range(0,ten):\n",
    "                # a 偶数位个数要补0\n",
    "                # b 奇数位个数\n",
    "                a,b = r - len(str(num)),0\n",
    "                for w in str(num):\n",
    "                    if int(w) % 2 == 0:\n",
    "                        a += 1\n",
    "                    else:\n",
    "                        b += 1\n",
    "                cnt[(a-b,num%k)] += 1\n",
    "            \n",
    "            # 查找left\n",
    "            res = 0\n",
    "            for num in range(1,lnum):\n",
    "                a,b = 0,0\n",
    "                if num != 0:\n",
    "                    for w in str(num):\n",
    "                        if int(w) % 2 == 0:\n",
    "                            a += 1\n",
    "                        else:\n",
    "                            b += 1\n",
    "                # 奇偶差值要对调，达到平衡\n",
    "                res += cnt[(b-a,(k-num*ten%k)%k)]\n",
    "            \n",
    "            # 当 left = lnum 时，right ∈ [0,rnum]\n",
    "            # 暴力\n",
    "            rnum = int(s[l:])\n",
    "            a,b = 0,0\n",
    "            for w in str(lnum):\n",
    "                if int(w) % 2 == 0:\n",
    "                    a += 1\n",
    "                else:\n",
    "                    b += 1\n",
    "            d = b - a\n",
    "            kmod = (k-lnum*ten%k)%k\n",
    "            \n",
    "            for num in range(0,rnum+1):\n",
    "                if num % k != kmod:\n",
    "                    continue\n",
    "                    \n",
    "                a,b = r - len(str(num)),0\n",
    "                for w in str(num):\n",
    "                    if int(w) % 2 == 0:\n",
    "                        a += 1\n",
    "                    else:\n",
    "                        b += 1\n",
    "                if a - b == d:\n",
    "                    res += 1\n",
    "            \n",
    "            # 当 left = 0 时，right ∈ [0,10^t)\n",
    "            # 暴力\n",
    "            for num in range(0,ten):\n",
    "                if num % k != 0:\n",
    "                    continue\n",
    "                \n",
    "                # 偶数位个数不需要补0\n",
    "                a,b = 0,0\n",
    "                for w in str(num):\n",
    "                    if int(w) % 2 == 0:\n",
    "                        a += 1\n",
    "                    else:\n",
    "                        b += 1\n",
    "                if a - b == 0:\n",
    "                    res += 1\n",
    "            \n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return getRes(high) - getRes(low-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def bias_mod(bias, mod, number, pos):\n",
    "            return (bias + 1 - 2 * (number % 2), (mod - number * pow(10, pos, k)) % k)\n",
    "        @cache\n",
    "        def free_digits(N, odd_bias, mod):\n",
    "            if N == 0:\n",
    "                return (odd_bias == 0) and (mod == 0)\n",
    "            if abs(odd_bias) > N:\n",
    "                return 0\n",
    "            if (odd_bias + N) % 2:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(10):\n",
    "                ans += free_digits(N - 1, *bias_mod(odd_bias, mod, i, N - 1))\n",
    "            return ans\n",
    "\n",
    "        def total(limit):\n",
    "            digits = [int(d) for d in str(limit)]\n",
    "            ans = 0\n",
    "            N = len(digits)\n",
    "            for i in range(1, N):\n",
    "                ans += free_digits(i, 0, 0) - free_digits(i - 1, 1, 0)\n",
    "            odd_bias = 0\n",
    "            mod = 0\n",
    "            for i, d in enumerate(digits):\n",
    "                for j in range(i == 0, d):\n",
    "                    ans += free_digits(N - i - 1, *bias_mod(odd_bias, mod, j, N - i - 1))\n",
    "                odd_bias, mod = bias_mod(odd_bias, mod, d, N - i - 1)\n",
    "            if odd_bias == 0 and mod == 0:\n",
    "                ans += 1\n",
    "            return ans\n",
    "        return total(high) - total(low - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def bias_mod(bias, mod, number, pos):\n",
    "            return (bias + 1 - 2 * (number % 2), (mod - number * pow(10, pos, k)) % k)\n",
    "        @cache\n",
    "        def free_digits(N, odd_bias, mod):\n",
    "            if N == 0:\n",
    "                return (odd_bias == 0) and (mod == 0)\n",
    "            if abs(odd_bias) > N:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(10):\n",
    "                ans += free_digits(N - 1, *bias_mod(odd_bias, mod, i, N - 1))\n",
    "            return ans\n",
    "\n",
    "        def total(limit):\n",
    "            digits = [int(d) for d in str(limit)]\n",
    "            ans = 0\n",
    "            N = len(digits)\n",
    "            for i in range(1, N):\n",
    "                ans += free_digits(i, 0, 0) - free_digits(i - 1, 1, 0)\n",
    "            odd_bias = 0\n",
    "            mod = 0\n",
    "            for i, d in enumerate(digits):\n",
    "                for j in range(i == 0, d):\n",
    "                    ans += free_digits(N - i - 1, *bias_mod(odd_bias, mod, j, N - i - 1))\n",
    "                odd_bias, mod = bias_mod(odd_bias, mod, d, N - i - 1)\n",
    "            if odd_bias == 0 and mod == 0:\n",
    "                ans += 1\n",
    "            return ans\n",
    "        return total(high) - total(low - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        low,high = map(lambda x:list(map(int,str(x))),[low,high])\n",
    "        low = [0]*(len(high)-len(low)) + low\n",
    "        n = len(low)\n",
    "        \n",
    "        @cache\n",
    "        def f(i,is_low,is_high,is_num,score,mod):\n",
    "            # print('\\t'*tab,i,is_low,is_high,is_num,score,mod)\n",
    "            if i == n: return int(is_num and score == 0 and mod == 0)\n",
    "            res = 0 if is_num or low[i] != 0 else f(i+1,is_low and low[i]==0,False,False,0,0)\n",
    "            if not is_num and (n-i) % 2 == 1: return res\n",
    "            low_val = low[i] if is_low else 0\n",
    "            high_val = high[i] if is_high else 9\n",
    "            # print('\\t'*tab,res,low_val,high_val)\n",
    "            mod = mod*10%k\n",
    "            for x in range(low_val,high_val+1):\n",
    "                if not is_num and x == 0: continue\n",
    "                res += f(i+1,is_low and x == low_val,is_high and x == high_val,True,score + (1 if x&1 else -1),(mod+x)%k)\n",
    "            # print('\\t'*tab,res)\n",
    "            return res\n",
    "        \n",
    "        return f(0,True,True,False,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\n",
    "        counts, totals = self.create(self.getLength(high), k)\n",
    "        # print(counts)\n",
    "        # print(totals)\n",
    "\n",
    "        lowCount = self.check(low, k, counts, totals)\n",
    "        # print(\"lowCount\",lowCount)\n",
    "\n",
    "        highCount = self.check(high, k, counts, totals)\n",
    "        # print(\"highCount\",highCount)\n",
    "\n",
    "        return highCount - lowCount + self.checkNum(high, k)\n",
    "\n",
    "    def getLength(self, num: int) -> List[int]:\n",
    "        length = 0\n",
    "        while num:\n",
    "            length += 1\n",
    "            num //= 10\n",
    "        return length\n",
    "\n",
    "    def create(self, length: int, k: int):\n",
    "        counts, totals = [[Counter() for _ in range(k)]], [0]\n",
    "        counts[0][0][0] = 1\n",
    "        for powers in range(length):\n",
    "            preCnts, curCnts = counts[-1], [Counter() for _ in range(k)]\n",
    "            for mod, preCnt in enumerate(preCnts):\n",
    "                for offer, total in preCnt.items():\n",
    "                    for num in range(1, 10):\n",
    "                        newMod = (mod + (10 ** powers) * num) % k\n",
    "                        newOffer = offer + 1 - ((num & 1) << 1)\n",
    "                        curCnts[newMod][newOffer] += total\n",
    "            \n",
    "            if powers > 1: totals.append(curCnts[0][0] + totals[powers - 1])\n",
    "            else: totals.append(curCnts[0][0])\n",
    "\n",
    "            for mod, preCnt in enumerate(preCnts):\n",
    "                for offer, total in preCnt.items():\n",
    "                    curCnts[mod][offer + 1] += total\n",
    "\n",
    "            counts.append(curCnts)\n",
    "        return counts, totals\n",
    "\n",
    "    def checkNum(self, num: int, k: int) -> int:\n",
    "        if num % k > 0: return 0\n",
    "        flag = 0\n",
    "        while num:\n",
    "            if num % 2: flag -= 1\n",
    "            else: flag += 1\n",
    "            num //= 10\n",
    "        return 0 if flag else 1\n",
    "\n",
    "    def check(self, num: int, k: int, counts, totals) -> int:\n",
    "        numOffer = 0\n",
    "        tempNum = num \n",
    "        while tempNum:\n",
    "            numOffer += 1 - ((tempNum & 1) << 1)\n",
    "            tempNum //= 10\n",
    "        sumOffer = 0\n",
    "        res = 0\n",
    "        idx = 0\n",
    "        while num:\n",
    "            modNum = num % 10\n",
    "            count = counts[idx]\n",
    "            # print(modNum)\n",
    "            num //= 10\n",
    "            head = 0 if num else 1\n",
    "            sumOffer += 1 - ((modNum & 1) << 1)\n",
    "            for i in range(head, modNum):\n",
    "                curMod = (k - ((num * 10 + i) * (10 ** idx) % k)) % k\n",
    "                curOffer = numOffer - sumOffer + 1 - ((i & 1) << 1)\n",
    "                # offer = ((i & 1) << 1) - 1\n",
    "                offer = -curOffer\n",
    "                # print(\"modNum\",modNum,\"num\",num,\"i\",i,\"curMod\",curMod,\"offer\",offer,\"mul\",(num * 10 + i) * (10 ** idx),\"mod\",(num * 10 + i) * (10 ** idx)%k)\n",
    "                # print(\"count\",count)\n",
    "                res += count[curMod][offer]\n",
    "\n",
    "            idx += 1\n",
    "        # print(\"res\",res,\"idx\",idx)\n",
    "        idx -= 1\n",
    "        # print(\"res\",res,\"base\",totals[idx & 1 ^ idx])\n",
    "        res += totals[idx & 1 ^ idx]\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        h = [pow(10, i) for i in range(10)]\n",
    "        low, high = str(low), str(high)\n",
    "        while len(low) < len(high):\n",
    "            low = \"0\" + low\n",
    "        m = len(high)\n",
    "        @cache\n",
    "        def dfs(totolLen, pos, restK, oddSubEven, islimitL, islimitH):\n",
    "            nonlocal k, m\n",
    "            base = m - totolLen\n",
    "            if pos == totolLen:\n",
    "                if restK == 0 and oddSubEven == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            f = 1 if pos == 0 else 0\n",
    "            res = 0\n",
    "            for i in range(f, 10):\n",
    "                if islimitL == 0 and i < int(low[base + pos]):\n",
    "                    continue\n",
    "                elif islimitH == 0 and i > int(high[base + pos]):\n",
    "                    continue\n",
    "                f1, f2 = islimitL, islimitH\n",
    "                if i > int(low[base + pos]):\n",
    "                    f1 = 1\n",
    "                if i < int(high[base + pos]):\n",
    "                    f2 = 1\n",
    "                if i & 1:\n",
    "                    add = 1\n",
    "                else:\n",
    "                    add = -1\n",
    "                res += dfs(totolLen, pos + 1, (restK + h[totolLen - pos - 1] * i) % k, oddSubEven + add, f1, f2)\n",
    "            return res\n",
    "        res = 0\n",
    "        for i in range(2, m + 1, 2):\n",
    "            if i < m:\n",
    "                if int(low[:(m - i)]) == 0:\n",
    "                    res += dfs(i, 0, 0, 0, 0, 1)\n",
    "            else:\n",
    "                res += dfs(i, 0, 0, 0, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def getRes(v):\n",
    "            s = str(v)\n",
    "            @cache\n",
    "            def calc(idx, start, bound, mod, diff):\n",
    "                if idx == len(s):\n",
    "                    if mod == 0 and diff == 0 and start: return 1\n",
    "                    return 0\n",
    "                \n",
    "                v = 0 if start else calc(idx+1, False, False, 0, 0)\n",
    "                \n",
    "                for i in (range(int(s[idx]) + 1) if bound else range(10)):\n",
    "                    if not start and i == 0: continue\n",
    "                    # 状态转移\n",
    "                    new_bound = bound and i == int(s[idx])\n",
    "                    new_mod = (10 * mod + i) % k\n",
    "                    new_diff = diff + 1 if i&1 else diff - 1\n",
    "                    v += calc(idx + 1, True, new_bound, new_mod, new_diff)\n",
    "                return v\n",
    "                \n",
    "            res = calc(0, False, True, 0, 0)\n",
    "            calc.cache_clear()\n",
    "            return res\n",
    "        \n",
    "        ans = getRes(high) - getRes(low - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        # 将两个数转化为长度相等的各数位的列表\n",
    "        low,high = map(lambda x:list(map(int,str(x))),[low,high])\n",
    "        low = [0]*(len(high)-len(low)) + low\n",
    "        n = len(low)\n",
    "        \n",
    "        # 记忆化搜索\n",
    "        @cache\n",
    "        def f(i,is_low,is_high,is_num,score,mod):\n",
    "            # 参数含义：位数，是否是最小值，是否是最大值，是否是数字，奇偶数目差，余数\n",
    "            if n-i < abs(score): return 0\n",
    "            # 如果到了最后一位，检查是否奇偶数位一样多，是否是数字，且余数为零\n",
    "            if i == n: return int(is_num and score == 0 and mod == 0)\n",
    "            # 如果还不是数字（前面没填过数），且较小的数字这一位是零，这里可以接着填零\n",
    "            res = 0 if is_num or low[i] != 0 else f(i+1,is_low and low[i]==0,False,False,0,0)\n",
    "            # 剪枝，如果剩余奇数个位置且还没开始填，那就不可能从这一位开始填\n",
    "            if not is_num and (n-i) % 2 == 1: return res\n",
    "            # 判别这一位可以选取的最小值和最大值\n",
    "            low_val = low[i] if is_low else 0\n",
    "            high_val = high[i] if is_high else 9\n",
    "            mod = mod*10%k\n",
    "            for x in range(low_val,high_val+1):\n",
    "                # 如果前面没填过数且这一位打算填，与之前的情况重复，跳过\n",
    "                if not is_num and x == 0: continue \n",
    "                res += f(i+1,is_low and x == low_val,is_high and x == high_val,True,score + (1 if x&1 else -1),(mod+x)%k)\n",
    "            return res\n",
    "        \n",
    "        return f(0,True,True,False,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def getRes(v):\n",
    "            s = str(v)\n",
    "            @cache\n",
    "            def calc(idx, start, bound, mod, diff):\n",
    "                if idx == len(s):\n",
    "                    if mod == 0 and diff == 0 and start: return 1\n",
    "                    return 0\n",
    "                \n",
    "                v = 0 if start else calc(idx+1, False, False, 0, 0)\n",
    "                \n",
    "                for i in (range(int(s[idx]) + 1) if bound else range(10)):\n",
    "                    if not start and i == 0: continue\n",
    "                    # 状态转移\n",
    "                    new_bound = bound and i == int(s[idx])\n",
    "                    new_mod = (10 * mod + i) % k\n",
    "                    new_diff = diff + 1 if i % 2 else diff - 1\n",
    "                    v += calc(idx + 1, True, new_bound, new_mod, new_diff)\n",
    "                return v\n",
    "                \n",
    "            res = calc(0, False, True, 0, 0)\n",
    "            calc.cache_clear()\n",
    "            return res\n",
    "        \n",
    "        ans = getRes(high) - getRes(low - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        h = [pow(10, i) for i in range(10)]\n",
    "        low, high = str(low), str(high)\n",
    "        while len(low) < len(high):\n",
    "            low = \"0\" + low\n",
    "        m = len(high)\n",
    "        @cache\n",
    "        def dfs(totolLen, pos, restK, oddSubEven, islimitL, islimitH):\n",
    "            nonlocal k, m\n",
    "            if totolLen - pos < abs(oddSubEven):\n",
    "                return 0\n",
    "            base = m - totolLen\n",
    "            if pos == totolLen:\n",
    "                if restK == 0 and oddSubEven == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            f = 1 if pos == 0 else 0\n",
    "            res = 0\n",
    "            for i in range(f, 10):\n",
    "                if islimitL == 0 and i < int(low[base + pos]):\n",
    "                    continue\n",
    "                elif islimitH == 0 and i > int(high[base + pos]):\n",
    "                    continue\n",
    "                f1, f2 = islimitL, islimitH\n",
    "                if i > int(low[base + pos]):\n",
    "                    f1 = 1\n",
    "                if i < int(high[base + pos]):\n",
    "                    f2 = 1\n",
    "                if i & 1:\n",
    "                    res += dfs(totolLen, pos + 1, (restK + h[totolLen - pos - 1] * i) % k, oddSubEven + 1, f1, f2)\n",
    "                else:\n",
    "                    res += dfs(totolLen, pos + 1, (restK + h[totolLen - pos - 1] * i) % k, oddSubEven - 1, f1, f2)\n",
    "            return res\n",
    "        res = 0\n",
    "        for i in range(2, m + 1, 2):\n",
    "            if i < m:\n",
    "                if int(low[:(m - i)]) == 0:\n",
    "                    res += dfs(i, 0, 0, 0, 0, 1)\n",
    "            else:\n",
    "                res += dfs(i, 0, 0, 0, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        Base = [1]\n",
    "        for i in range(10):\n",
    "            Base.append(Base[-1]*10)\n",
    "\n",
    "        @cache\n",
    "        def dfs(index, oddCount, mod):\n",
    "            if index == -1:\n",
    "                return oddCount == 0 and mod == 0\n",
    "            if oddCount < 0:\n",
    "                return 0\n",
    "            if index == 0:\n",
    "                ret = 0\n",
    "                for i in range(10):\n",
    "                    if oddCount == i%2 and i%k == mod:\n",
    "                        ret += 1\n",
    "                return ret\n",
    "\n",
    "            ret = 0\n",
    "            for i in range(10):\n",
    "                t = dfs(index-1, oddCount-i%2, (mod-i*Base[index]%k+k)%k)\n",
    "                ret += t\n",
    "            return ret\n",
    "        \n",
    "\n",
    "        def getCount(num):\n",
    "            if num == 0:\n",
    "                return 0\n",
    "            t = num\n",
    "            # length = 0\n",
    "            base = 1\n",
    "            digits = []\n",
    "            while t:\n",
    "                digits.append(t%10)\n",
    "                # length += 1\n",
    "                t //= 10\n",
    "                base *= 10\n",
    "                \n",
    "            print(digits)\n",
    "            oddCount = 0\n",
    "            ret = 0\n",
    "            prefix = 0\n",
    "            if len(digits) % 2 == 0:\n",
    "                for index, digit in list(enumerate(digits))[::-1]:\n",
    "                    base //= 10\n",
    "                    if index+1 ==len(digits):\n",
    "                        for i in range(1, digit):\n",
    "                            ret += dfs(index-1, len(digits)//2-i%2, (k-i*Base[index]%k)%k)\n",
    "                            # print(i, index-1, len(digits)//2-i%2, (k-i*Base[index]%k)%k, dfs(index-1, len(digits)//2-i%2, (k-i*Base[index]%k)%k))\n",
    "                    else:\n",
    "                        for i in range(0, digit):\n",
    "                            ret += dfs(index-1, len(digits)//2-oddCount - i%2, (k-(prefix+i*Base[index])%k)%k)\n",
    "                            # print(i, index-1, len(digits)//2-oddCount, (k-prefix%k)%k, dfs(index-1, len(digits)//2-oddCount, (k-prefix%k)%k))\n",
    "                        \n",
    "                # print\n",
    "                    oddCount += digit%2\n",
    "                    prefix += digit*Base[index]\n",
    "                    # print(index, digit, ret)\n",
    "            \n",
    "            for i in range(len(digits)-1):\n",
    "                if (i + 1) % 2 == 0:\n",
    "                    for j in range(1, 10):\n",
    "                        ret += dfs(i-1, (i+1)//2-j%2, (k-j*Base[i]%k)%k)\n",
    "\n",
    "            if prefix%k== 0 and oddCount==len(digits)//2 and len(digits)%2==0:\n",
    "                return ret + 1\n",
    "            else:\n",
    "                return ret            \n",
    "\n",
    "\n",
    "        \n",
    "        print(getCount(high), getCount(low-1))\n",
    "        return getCount(high) - getCount(low-1)\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        h = [pow(10, i) for i in range(10)]\n",
    "        low, high = str(low), str(high)\n",
    "        while len(low) < len(high):\n",
    "            low = \"0\" + low\n",
    "        m = len(high)\n",
    "        @cache\n",
    "        def dfs(totolLen, pos, restK, oddSubEven, islimitL, islimitH):\n",
    "            nonlocal k, m\n",
    "            if totolLen - pos < abs(oddSubEven):\n",
    "                return 0\n",
    "            base = m - totolLen\n",
    "            if pos == totolLen:\n",
    "                if restK == 0 and oddSubEven == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            f = 1 if pos == 0 else 0\n",
    "            res = 0\n",
    "            for i in range(f, 10):\n",
    "                if islimitL == 0 and i < int(low[base + pos]):\n",
    "                    continue\n",
    "                elif islimitH == 0 and i > int(high[base + pos]):\n",
    "                    continue\n",
    "                f1, f2 = islimitL, islimitH\n",
    "                if i > int(low[base + pos]):\n",
    "                    f1 = 1\n",
    "                if i < int(high[base + pos]):\n",
    "                    f2 = 1\n",
    "                if i & 1:\n",
    "                    res += dfs(totolLen, pos + 1, (restK + h[totolLen - pos - 1] * i) % k, oddSubEven + 1, f1, f2)\n",
    "                else:\n",
    "                    res += dfs(totolLen, pos + 1, (restK + h[totolLen - pos - 1] * i) % k, oddSubEven - 1, f1, f2)\n",
    "            return res\n",
    "        res = 0\n",
    "        for i in range(2, m + 1, 2):\n",
    "            if i < m:\n",
    "                if int(low[:(m - i)]) == 0:\n",
    "                    res += dfs(i, 0, 0, 0, 0, 1)\n",
    "            else:\n",
    "                res += dfs(i, 0, 0, 0, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(first, odd, even, residual, limit: str):\n",
    "            # number of beatiful num less and equal than limit\n",
    "            nonlocal k\n",
    "            if odd == 0 and even == 0:\n",
    "                return int(residual == 0)\n",
    "\n",
    "            ans = 0\n",
    "            if odd:\n",
    "                for o in range(1, min(9, int(limit[0])) + 1, 2):\n",
    "                    li = limit[1:] if str(o) == limit[0] else '9'*len(limit[1:])\n",
    "                    ans += dfs(False, odd-1, even, (residual * 10 + o) % k, li)\n",
    "\n",
    "            if even:\n",
    "                if not first:\n",
    "                    li = limit[1:] if str(0) == limit[0] else '9' * len(limit[1:])\n",
    "                    ans += dfs(False, odd, even - 1, (residual * 10) % k, li)\n",
    "                for e in range(2, min(8, int(limit[0])) + 1, 2):\n",
    "                    li = limit[1:] if str(e) == limit[0] else '9' * len(limit[1:])\n",
    "                    ans += dfs(False, odd, even-1, (residual * 10 + e) % k, li)\n",
    "\n",
    "\n",
    "            return ans\n",
    "\n",
    "        answer = 0\n",
    "        low_length = len(str(low-1))\n",
    "        high_length = len(str(high))\n",
    "\n",
    "        for kk in range(2, high_length+1, 2):\n",
    "            if kk < high_length:\n",
    "                answer += dfs(True, kk//2, kk //2, 0, str(9)*kk)\n",
    "            else:\n",
    "                answer += dfs(True, kk // 2, kk // 2, 0, str(high))\n",
    "\n",
    "        for kk in range(2, low_length + 1, 2):\n",
    "            if kk < low_length:\n",
    "                answer -= dfs(True, kk // 2, kk // 2, 0, str(9) * kk)\n",
    "            else:\n",
    "                answer -= dfs(True, kk // 2, kk // 2, 0, str(low-1))\n",
    "\n",
    "        return answer\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, su: int, ecnt: int, ocnt: int, islimit: int, isnum: int):\n",
    "            if i == n:\n",
    "                return 1 if isnum and su == 0 and ecnt == ocnt else 0\n",
    "            cnt = dfs(i + 1, su, 0, 0, 0, isnum) if not isnum else 0\n",
    "            digit = int(s[i])\n",
    "            ub = digit if islimit else 9\n",
    "            for d in range(1 - isnum, ub + 1):\n",
    "                if d % 2 == 0:\n",
    "                    cnt += dfs(i + 1, (su*10 + d) % k, ecnt + 1, ocnt, int(islimit and d == digit), 1)\n",
    "                else:\n",
    "                    cnt += dfs(i + 1, (su*10 + d) % k, ecnt, ocnt + 1, int(islimit and d == digit), 1)\n",
    "            return cnt\n",
    "        s = str(low - 1)\n",
    "        n = len(s)\n",
    "        cnt1 = dfs(0, 0, 0, 0, 1, 0)\n",
    "        dfs.cache_clear()\n",
    "        s = str(high)\n",
    "        n = len(s)\n",
    "        cnt2 = dfs(0, 0, 0, 0, 1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return cnt2 - cnt1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(length: int, mod: int, diff: int) -> int:\n",
    "            if length == 0: return 1 if mod == diff == 0 else 0\n",
    "            curLength = length - 1\n",
    "            tens = 10 ** curLength\n",
    "            res = 0\n",
    "            for num in range(10):\n",
    "                preMod = (k + (mod - tens * num) % k) % k\n",
    "                numDiff = 1 - ((num & 1) << 1)\n",
    "                res += dfs(curLength, preMod, diff - numDiff)\n",
    "            return res\n",
    "\n",
    "\n",
    "\n",
    "        def dp(num: int) -> int:\n",
    "            numDiff, avatarNum = 0, num * 10\n",
    "            while (avatarNum := avatarNum // 10): numDiff += 1 - ((avatarNum & 1) << 1)\n",
    "                \n",
    "            res = length = sumDiff = 0\n",
    "\n",
    "            while num:\n",
    "                modNum = num % 10\n",
    "                num //= 10\n",
    "                head = 0 if num else 1\n",
    "                sumDiff += 1 - ((modNum & 1) << 1)\n",
    "                for i in range(head, modNum):\n",
    "                    curMod = (k - ((num * 10 + i) * (10 ** length) % k)) % k\n",
    "                    curDiff = numDiff - sumDiff + 1 - ((i & 1) << 1)\n",
    "                    # offer = -curDiff\n",
    "                    # res += count[curMod][offer]\n",
    "                    res += dfs(length, curMod, -curDiff)\n",
    "\n",
    "                if length & 1 == 0 and length > 0:\n",
    "                    curLength = length - 1\n",
    "                    tens = 10 ** curLength\n",
    "                    for i in range(1, 10):\n",
    "                        curMod = (k - (i * tens % k)) % k\n",
    "                        curDiff = 1 - ((i & 1) << 1)\n",
    "                        res += dfs(curLength, curMod, -curDiff)\n",
    "                \n",
    "                length += 1\n",
    "\n",
    "            # length -= 1\n",
    "            # res += totals[length & 1 ^ length]\n",
    "                \n",
    "            return res\n",
    "\n",
    "        print(dp(high))\n",
    "\n",
    "        return dp(high) - dp(low) + self.checkNum(high, k)\n",
    "        \n",
    "        \n",
    "        # counts, totals = self.create(self.getLength(high), k)\n",
    "        # # print(counts)\n",
    "        # # print(totals)\n",
    "\n",
    "        # lowCount = self.check(low, k, counts, totals)\n",
    "        # # print(\"lowCount\",lowCount)\n",
    "\n",
    "        # highCount = self.check(high, k, counts, totals)\n",
    "        # print(\"highCount\",highCount)\n",
    "\n",
    "        # return highCount - lowCount + self.checkNum(high, k)\n",
    "\n",
    "\n",
    "    def checkNum(self, num: int, k: int) -> int:\n",
    "        if num % k > 0: return 0\n",
    "        flag = 0\n",
    "        while num:\n",
    "            if num % 2: flag -= 1\n",
    "            else: flag += 1\n",
    "            num //= 10\n",
    "        return 0 if flag else 1\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        from functools import cache\n",
    "        h=str(high)\n",
    "        l=str(low-1)\n",
    "        @cache\n",
    "        def get(s,a,b,c,d,e):\n",
    "            if len(s)%2 !=0:s='9'*(len(s)-1)\n",
    "            if len(s)==1:return 0\n",
    "            if a==len(s):\n",
    "                if d==0 and b==len(s)/2 and e:\n",
    "                    return 1\n",
    "                else :return 0\n",
    "            res=0\n",
    "            up=int(s[a]) if c else 9\n",
    "            for i in range(up+1):\n",
    "                if i==0 and not e:\n",
    "                    if a+3<len(s):\n",
    "                        res+=get(s[2:],a,0,False,d,False)\n",
    "                elif (b+i%2)<=len(s)/2  and (a+1-b-i%2)<=len(s)/2:\n",
    "                    res+=get(s,a+1,b+i%2,c and i==int(s[a]),(d+i*10**(len(s)-a-1))%k,True)\n",
    "            return res\n",
    "        return get(h,0,0,True,0,False)-get(l,0,0,True,0,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        upper = str(high)\n",
    "        n = len(upper)\n",
    "        lower = str(low).zfill(n)\n",
    "\n",
    "        ##############################################\n",
    "        # Template: Digit DP\n",
    "\n",
    "        # if a numeric string needs to be padded with prefix zeros, use s.zfill(n)\n",
    "        # make sure variable \"upper\", \"lower\", \"n\" are defined\n",
    "\n",
    "        @functools.cache\n",
    "        def dp(\n",
    "                i=0,  # the current bit (from left)\n",
    "                rem=0, diff=0,  # define your special conditions here\n",
    "                UL=True, DL=True, valid=False,  # digit limitations\n",
    "        ):\n",
    "            nonlocal upper, lower, n\n",
    "            if i == n:  # break condition\n",
    "                # caution when lower == 0!\n",
    "                # print(i, rem, diff, UL, DL, valid, int(valid) and rem == 0 and diff == 0)\n",
    "                return int(valid) and \\\n",
    "                       rem == 0 and diff == 0\n",
    "            up = int(upper[i]) if UL else 9\n",
    "            down = int(lower[i]) if DL or not valid else 0\n",
    "            ans = 0\n",
    "            for d in range(down, up + 1):\n",
    "                # filter with special conditions here\n",
    "\n",
    "                ans += dp(\n",
    "                    i + 1,\n",
    "                    (rem * 10 + d) % k,\n",
    "                    0 if d == 0 and not valid else (diff + d % 2 * 2 - 1),\n",
    "                    UL=(d == up and UL),\n",
    "                    DL=(d == down and DL),\n",
    "                    valid=(valid or d > 0),\n",
    "                )\n",
    "            # print(i, rem, diff, UL, DL, valid, ans)\n",
    "            return ans\n",
    "        ##############################################\n",
    "\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        Base = [1]\n",
    "        for i in range(10):\n",
    "            Base.append(Base[-1]*10)\n",
    "\n",
    "        @cache\n",
    "        def dfs(index, oddCount, mod):\n",
    "            if index == -1:\n",
    "                return oddCount == 0 and mod == 0\n",
    "            if oddCount < 0:\n",
    "                return 0\n",
    "            if index == 0:\n",
    "                ret = 0\n",
    "                for i in range(10):\n",
    "                    if oddCount == i%2 and i%k == mod:\n",
    "                        ret += 1\n",
    "                return ret\n",
    "\n",
    "            ret = 0\n",
    "            for i in range(10):\n",
    "                t = dfs(index-1, oddCount-i%2, (mod-i*Base[index]%k+k)%k)\n",
    "                ret += t\n",
    "            return ret\n",
    "        \n",
    "\n",
    "        def getCount(num):\n",
    "            if num == 0:\n",
    "                return 0\n",
    "            t = num\n",
    "            # length = 0\n",
    "            base = 1\n",
    "            digits = []\n",
    "            while t:\n",
    "                digits.append(t%10)\n",
    "                # length += 1\n",
    "                t //= 10\n",
    "                base *= 10\n",
    "                \n",
    "            print(digits)\n",
    "            oddCount = 0\n",
    "            ret = 0\n",
    "            prefix = 0\n",
    "            if len(digits) % 2 == 0:\n",
    "                for index, digit in list(enumerate(digits))[::-1]:\n",
    "                    base //= 10\n",
    "                    if index+1 ==len(digits):\n",
    "                        for i in range(1, digit):\n",
    "                            ret += dfs(index-1, len(digits)//2-i%2, (k-i*Base[index]%k)%k)\n",
    "                            print(i, index-1, len(digits)//2-i%2, (k-i*Base[index]%k)%k, dfs(index-1, len(digits)//2-i%2, (k-i*Base[index]%k)%k))\n",
    "                    else:\n",
    "                        for i in range(0, digit):\n",
    "                            ret += dfs(index-1, len(digits)//2-oddCount - i%2, (k-(prefix+i*Base[index])%k)%k)\n",
    "                            # print(i, index-1, len(digits)//2-oddCount, (k-prefix%k)%k, dfs(index-1, len(digits)//2-oddCount, (k-prefix%k)%k))\n",
    "                        \n",
    "                # print\n",
    "                    oddCount += digit%2\n",
    "                    prefix += digit*Base[index]\n",
    "                    print(index, digit, ret)\n",
    "            \n",
    "            for i in range(len(digits)-1):\n",
    "                if (i + 1) % 2 == 0:\n",
    "                    for j in range(1, 10):\n",
    "                        ret += dfs(i-1, (i+1)//2-j%2, (k-j*Base[i]%k)%k)\n",
    "\n",
    "            if prefix%k== 0 and oddCount==len(digits)//2 and len(digits)%2==0:\n",
    "                return ret + 1\n",
    "            else:\n",
    "                return ret            \n",
    "\n",
    "\n",
    "        \n",
    "        print(getCount(high), getCount(low-1))\n",
    "        return getCount(high) - getCount(low-1)\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://space.bilibili.com/206214\n",
    "class Solution:\n",
    "\tdef numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\t\tlow_s = str(low)\n",
    "\t\thigh_s = str(high)\n",
    "\t\tn = len(high_s)\n",
    "\t\tlow_s = '0' * (n - len(low_s)) + low_s\n",
    "\t\t@cache\n",
    "\t\tdef dfs(i: int, val: int, diff: int, limit_low: bool, limit_up: bool, is_num: bool) -> int:\n",
    "\t\t\tif i == n:\n",
    "\t\t\t\treturn int(is_num and val == 0 and diff == 0)\n",
    "\t\t\tres = 0\n",
    "\t\t\tif not is_num and low_s[i] == '0':\n",
    "\t\t\t\tres = dfs(i + 1, val, diff, True, False, False)\n",
    "\t\t\tlo = int(low_s[i]) if limit_low else 0\n",
    "\t\t\tup = int(high_s[i]) if limit_up else 9 \n",
    "\t\t\tfor d in range(max(lo, 1-is_num), up + 1):\n",
    "\t\t\t\tres += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, limit_low and d == lo, limit_up and d == up, True)\n",
    "\t\t\treturn res\n",
    "\t\treturn dfs(0, 0, 0, True, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        H = str(high)\n",
    "        L = str(low).zfill(len(H))\n",
    "        @cache\n",
    "        def dfs(i,st1,st2,st3,lbd,ubd):\n",
    "            if i==len(H):\n",
    "                return st1==st2==0\n",
    "            res = 0\n",
    "            U = int(H[i]) if ubd else 9\n",
    "            D = int(L[i]) if lbd else 0\n",
    "            for x in range(D,U+1):\n",
    "                res += dfs(i+1,st1+(0 if st3 and x==0 else 1 if x%2 else -1),(st2*10+x)%k,st3 and x==0,lbd and x==D,ubd and x==U)\n",
    "            return res\n",
    "        return dfs(0,0,0,True,True,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        # 小于等于limit（limit为字符串）的整数个数，要求奇数数位比偶数数位多a，除以k余b，first代表最高位是否是首位\n",
    "        @cache\n",
    "        def dp(limit, a, b, first):\n",
    "            if not limit:\n",
    "                return int(a == b == 0)\n",
    "            # 已经无法满足奇偶数位要求\n",
    "            if abs(a) > len(limit):\n",
    "                return 0\n",
    "            ret = 0\n",
    "            # 枚举最高位\n",
    "            for i in range(min(9, int(limit[0])) + 1):\n",
    "                # 首位为0时,可以不计入偶数数位\n",
    "                if i == 0 and first:\n",
    "                    ret += dp('9' * (len(limit) - 1), a, b, True)\n",
    "                else:\n",
    "                    aa = a - (1 if i % 2 else -1)  # 如果i是奇数，则所需奇偶数位差减1，否则加1\n",
    "                    bb = (b - i * 10 ** (len(limit) - 1)) % k  # 需要剩余部分除以k余bb\n",
    "                    if i < int(limit[0]):\n",
    "                        ret += dp('9' * (len(limit) - 1), aa, bb, False)\n",
    "                    else:\n",
    "                        ret += dp(limit[1:], aa, bb, False)\n",
    "            return ret\n",
    "\n",
    "        return dp(str(high), 0, 0, True) - dp(str(low - 1), 0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        # 小于等于limit（limit为字符串）的整数个数，要求奇数数位比偶数数位多a，除以k余b，first代表最高位是否是首位\n",
    "        @cache\n",
    "        def dp(limit, a, b, first):\n",
    "            if not limit:\n",
    "                return int(a == b == 0)\n",
    "            # 已经无法满足奇偶数位要求\n",
    "            if abs(a) > len(limit):\n",
    "                return 0\n",
    "            ret = 0\n",
    "            # 枚举最高位\n",
    "            for i in range(min(9, int(limit[0])) + 1):\n",
    "                # 首位为0时,可以不计入偶数数位\n",
    "                if i == 0 and first:\n",
    "                    ret += dp('9' * (len(limit) - 1), a, b, True)\n",
    "                else:\n",
    "                    aa = a - (1 if i % 2 else -1)  # 如果i是奇数，则所需奇偶数位差减1，否则加1\n",
    "                    bb = (b - i * pow(10, len(limit) - 1, k)) % k  # 需要剩余部分除以k余bb\n",
    "                    if i < int(limit[0]):\n",
    "                        ret += dp('9' * (len(limit) - 1), aa, bb, False)\n",
    "                    else:\n",
    "                        ret += dp(limit[1:], aa, bb, False)\n",
    "            return ret\n",
    "\n",
    "        return dp(str(high), 0, 0, True) - dp(str(low - 1), 0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def OkOddEven(isStart, odd, even, left):\n",
    "            if isStart:\n",
    "                for x in range(0, left + 1):\n",
    "                    if (odd + x) == (even + left - x):\n",
    "                        return True\n",
    "                return False\n",
    "            else:\n",
    "                if (odd + left) < even or (even + left) < odd:\n",
    "                    return False\n",
    "                return True\n",
    "\n",
    "        def search(ss):\n",
    "            import functools\n",
    "            @functools.cache\n",
    "            def f(i, isLimit, isStart, odd, even, value):\n",
    "                # print(i, isLimit, isStart, odd, even, value)\n",
    "                if i == len(ss):\n",
    "                    if not isStart: return 0\n",
    "                    if odd == even and value % k == 0:\n",
    "                        # print(value)\n",
    "                        return 1\n",
    "                    return 0\n",
    "\n",
    "                left = len(ss) - i\n",
    "                if not OkOddEven(isStart, odd, even, left):\n",
    "                    return 0\n",
    "\n",
    "                ans = 0\n",
    "                if not isStart:\n",
    "                    ans += f(i + 1, True, False, odd, even, value)\n",
    "\n",
    "                from_value = 1 if not isStart else 0\n",
    "                to_value = int(ss[i]) if not isLimit else 9\n",
    "                for x in range(from_value, to_value + 1):\n",
    "                    ans += f(i + 1, isLimit or x < int(ss[i]), isStart or x != 0,\n",
    "                             odd + (x % 2), even + (x + 1) % 2,\n",
    "                             # value * 10 + x)\n",
    "                             (value * 10 + x) % k)\n",
    "                return ans\n",
    "\n",
    "            return f(0, False, False, 0, 0, 0)\n",
    "\n",
    "        h = search(str(high))\n",
    "        l = search(str(low - 1))\n",
    "        ans = h - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s: str):\n",
    "            n = len(s)\n",
    "            @cache\n",
    "            def ff(i: int, diff: int, v: int, allLimit: bool, filled: bool) -> int:\n",
    "                if abs(diff) > n - i:\n",
    "                    return 0\n",
    "                if i == n:\n",
    "                    if v: return 0\n",
    "                    return int(diff == 0)\n",
    "                res, cur = 0, int(s[i])\n",
    "                if not filled:\n",
    "                    res += ff(i + 1, 0, 0, False, False)\n",
    "                bottom, up = 0 if filled else 1, cur if allLimit else 9\n",
    "                for d in range(bottom, up + 1):\n",
    "                    res += ff(i + 1, diff + (1 if d & 1 else -1), (v * 10 + d) % k, allLimit and d == up, True)\n",
    "                return res\n",
    "            return ff(0, 0, 0, True, False)\n",
    "        return f(str(high)) - f(str(low - 1))\n",
    "        \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s):\n",
    "            @cache\n",
    "            def solve(i: int, cur_num, sum1, is_limit, first_zero):\n",
    "                if abs(sum1) > len(s) //2: return 0\n",
    "                if i == len(s):\n",
    "                    return int(sum1 == 0 and cur_num % k == 0 and first_zero == False)\n",
    "                res = 0\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(up + 1):\n",
    "                    if first_zero and d == 0:\n",
    "                        res += solve(i + 1, cur_num, sum1, is_limit and d == up, first_zero and d == 0)\n",
    "                    elif d % 2 == 0:\n",
    "                        tmp = (cur_num + d * pow(10, len(s) - 1 - i)) % k\n",
    "                        res += solve(i + 1, tmp, sum1 + 1, is_limit and d == up, first_zero and d == 0)\n",
    "                    else:\n",
    "                        tmp = (cur_num + d * pow(10, len(s) - 1 - i)) % k\n",
    "                        res += solve(i + 1, tmp, sum1 - 1, is_limit and d == up, first_zero and d == 0)\n",
    "                return res\n",
    "            return solve(0, 0, 0, True, True)\n",
    "\n",
    "        min_res = 0\n",
    "        num11, num22 = 0, 0\n",
    "        for s_i in str(low):\n",
    "            if int(s_i) % 2 == 0:\n",
    "                num11 += 1\n",
    "            else:\n",
    "                num22 += 1\n",
    "        if num11 == num22 and low % k == 0:\n",
    "            min_res += 1\n",
    "        ans = f(str(high)) - f(str(low)) + min_res\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        dp = []\n",
    "        dp.append([\n",
    "            [[0]*k\n",
    "            for i in range(21)]\n",
    "            for j in range(10)\n",
    "        ])\n",
    "        for i in range(10):\n",
    "            dp[0][i][(1 if i %2 else -1)+10][i%k] += 1\n",
    "        \n",
    "        base = 1\n",
    "        for i in range(9):\n",
    "            base *= 10\n",
    "            tmp = [\n",
    "                [[0]*k\n",
    "                for l in range(21)]\n",
    "                for j in range(10)\n",
    "            ]\n",
    "            for j in range(10):\n",
    "                for k2 in range(21):\n",
    "                    for l in range(k):\n",
    "                        if not dp[i][j][k2][l]: continue\n",
    "                        # print(i, j, k2, l, dp[i][j][k2][l])\n",
    "                        for j2 in range(10):\n",
    "                            num = j2*base\n",
    "                            tmp[j2]\n",
    "                            tmp[j2][(1 if j2 %2 else -1)+k2]\n",
    "                            tmp[j2] \\\n",
    "                            [(1 if j2 %2 else -1)+k2] \\\n",
    "                            [(l+num)%k] += dp[i][j][k2][l]\n",
    "            dp.append(tmp)\n",
    "            \n",
    "        # print(dp)\n",
    "        \n",
    "        def getCount(num):\n",
    "            if num == 0:\n",
    "                return 0\n",
    "            t = num\n",
    "            # length = 0\n",
    "            base = 1\n",
    "            digits = []\n",
    "            while t:\n",
    "                digits.append(t%10)\n",
    "                # length += 1\n",
    "                t //= 10\n",
    "                base *= 10\n",
    "                \n",
    "            # print(digits)\n",
    "            minus = 0\n",
    "            ret = 0\n",
    "            prefix = 0\n",
    "            for index, digit in list(enumerate(digits))[::-1]:\n",
    "                base //= 10\n",
    "                if index+1 ==len(digits):\n",
    "                        for i in range(1, digit):\n",
    "                            ret += dp[index][i][10][0]\n",
    "                        # ret += dp[index][0][9][0]\n",
    "                else:\n",
    "                    for i in range(0, digit):\n",
    "                        ret += dp[index][i][10-minus][(k-prefix%k)%k]\n",
    "\n",
    "                # print\n",
    "                minus += (1 if digit %2 else -1)\n",
    "                prefix += digit*base\n",
    "                # print(index, digit, ret)\n",
    "            \n",
    "            for i in range(len(digits)-1):\n",
    "                for j in range(1, 10):\n",
    "                    ret += dp[i][j][10][0]\n",
    "\n",
    "            if prefix%k== 0 and minus==0:\n",
    "                return ret + 1\n",
    "            else:\n",
    "                return ret\n",
    "        \n",
    "        # print(getCount(high), getCount(low-1))\n",
    "        return getCount(high) - getCount(low-1)\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cal(self, x:int, k:int) ->int:\n",
    "        s = str(x)\n",
    "        @cache\n",
    "        def f(i: int, cur: int, is_limit: bool, is_num: bool, flag: int) -> int:\n",
    "            # 终点\n",
    "            if i == len(s):\n",
    "                return int(is_num) and flag == 0 and cur % k == 0\n",
    "            if len(s) - abs(flag) < abs(flag): return 0\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位, 不填数字\n",
    "                res = f(i + 1, cur, False, False, flag)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(0 if is_num else 1, up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, (cur * 10 + d) % k, is_limit and d == up, True, flag + (1 if d % 2 == 0 else -1))\n",
    "            return res\n",
    "        return f(0, 0, True, False, 0)\n",
    "        \n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        \n",
    "        return self.cal(high, k) - self.cal(low-1, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def printf(func):\n",
    "    def wrapper(*args):\n",
    "        ret = func(*args)\n",
    "        print (args, ret)\n",
    "        return ret\n",
    "    return wrapper\n",
    "\n",
    "def u(i):\n",
    "    return i % 2 * 2 - 1\n",
    "\n",
    "#@printf\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def f(high: str, x: int, y: int, lz: bool) -> int:\n",
    "            if len(high) == 1:\n",
    "                if lz:\n",
    "                    return sum(int((i + x) % k == 0 and u(i) + y == 0) for i in range(int(high) + 1))\n",
    "                else:\n",
    "                    return sum(int((i + x) % k == 0 and u(i) + y == 0) for i in range(1, int(high) + 1))\n",
    "            else:\n",
    "                t9 = '9' * (len(high) - 1)\n",
    "                t10 = int(t9) + 1\n",
    "                i0 = int(high[0])\n",
    "                if lz:\n",
    "                    return sum(f(t9, (x + t10 * i) % k, y + u(i), True) for i in range(i0)) + f(high[1:], (x + i0 * t10) % k, y + u(i0), True)\n",
    "                else:\n",
    "                    ret1 = sum(f(t9, (x + t10 * i) % k, y + u(i), True) for i in range(1, i0))\n",
    "                    ret2 = f(t9, x % k, y, False)\n",
    "                    ret3 = f(high[1:], (x + i0 * t10) % k, y + u(i0), True)\n",
    "                    return ret1 + ret2 + ret3\n",
    "        return f(str(high), 0, 0, False) - f(str(low - 1), 0, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        s = str(high) # 允许的范围是 [1,n]\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, diff: int, m: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(is_num and diff == 0 and m == 0)  # is_num 为 True 表示得到了一个合法数字\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res = f(i + 1, diff, m, False, False)\n",
    "            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1,diff+1 if (d % 2) else diff-1, (m*10+d)%k, is_limit and d == up, True)\n",
    "            return res\n",
    "        a1 = f(0, 0, 0, True, False)\n",
    "        s = str(low-1) # 允许的范围是 [1,n]\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, diff: int, m: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(is_num and diff == 0 and m == 0)  # is_num 为 True 表示得到了一个合法数字\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res = f(i + 1, diff, m, False, False)\n",
    "            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1,diff+1 if (d % 2) else diff-1, (m*10+d)%k, is_limit and d == up, True)\n",
    "            return res\n",
    "        a2 = f(0, 0, 0, True, False)\n",
    "        return a1-a2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s):\n",
    "            @cache\n",
    "            def solve(i: int, cur_num, sum1, is_limit, first_zero):\n",
    "                if abs(sum1) > len(s) //2: return 0\n",
    "                if i == len(s):\n",
    "                    return int(sum1 == 0 and cur_num % k == 0 and first_zero == False)\n",
    "                res = 0\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(up + 1):\n",
    "                    print('i, d = ', i,  d)\n",
    "                    if first_zero and d == 0:\n",
    "                        res += solve(i + 1, cur_num, sum1, is_limit and d == up, first_zero and d == 0)\n",
    "                    elif d % 2 == 0:\n",
    "                        tmp = (cur_num + d * pow(10, len(s) - 1 - i)) % k\n",
    "                        res += solve(i + 1, tmp, sum1 + 1, is_limit and d == up, first_zero and d == 0)\n",
    "                    else:\n",
    "                        tmp = (cur_num + d * pow(10, len(s) - 1 - i)) % k\n",
    "                        res += solve(i + 1, tmp, sum1 - 1, is_limit and d == up, first_zero and d == 0)\n",
    "                return res\n",
    "            return solve(0, 0, 0, True, True)\n",
    "\n",
    "        min_res = 0\n",
    "        num11, num22 = 0, 0\n",
    "        for s_i in str(low):\n",
    "            if int(s_i) % 2 == 0:\n",
    "                num11 += 1\n",
    "            else:\n",
    "                num22 += 1\n",
    "        if num11 == num22 and low % k == 0:\n",
    "            min_res += 1\n",
    "        ans = f(str(high)) - f(str(low)) + min_res\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        a = [1, -1]\n",
    "        @cache\n",
    "        def dfs(s, idx:int, limit:bool, pre:int, is_num: bool, flag):\n",
    "            if idx == len(s):\n",
    "                return (pre == 0 and flag == 0 and is_num)\n",
    "\n",
    "            if not is_num and (len(s) - idx) % 2:\n",
    "                return int(dfs(s, idx+1, False, 0, False, 0))\n",
    "            res = 0\n",
    "            up = int(s[idx]) if limit else 9\n",
    "            for i in range(up + 1):\n",
    "                res += dfs(s, idx+1, limit and i == up, (pre * 10 + i)% k, is_num or i > 0, flag - a[i % 2])\n",
    "            return res\n",
    "        # print(dfs(str(high), 0, True, 0, False, 0), dfs(str(16), 0, True, 0, False, 0))\n",
    "        return dfs(str(high), 0, True, 0, False, 0) - dfs(str(low - 1), 0, True, 0, False, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def f(n, i, dif, r, equal, pos):\n",
    "            if abs(dif) > i+1:\n",
    "                return 0\n",
    "            if i == -1:\n",
    "                return int(dif == r == 0 and pos)\n",
    "            t = n//10**i % 10 if equal else 9\n",
    "            ans = 0\n",
    "            for j in range(t+1):\n",
    "                x = 1 if j % 2 == 0 else -1\n",
    "                if not pos and j == 0:\n",
    "                    x = 0\n",
    "                eq = equal and j == t\n",
    "                ans += f(n, i-1, dif+x, (r + j * 10**i) % k, eq, pos or j>0)\n",
    "            return ans\n",
    "        \n",
    "        i1, i2 = len(str(low-1))-1, len(str(high))-1\n",
    "        return f(high, i2, 0, 0, True, False) - f(low-1, i1, 0, 0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s):\n",
    "            @cache\n",
    "            def solve(i: int, cur_num, sum1, is_limit, first_zero):\n",
    "                if abs(sum1) > len(s) //2: return 0\n",
    "                if i == len(s):\n",
    "                    result = int(sum1 == 0 and cur_num % k == 0 and first_zero == False)\n",
    "                    return int(sum1 == 0 and cur_num % k == 0 and first_zero == False)\n",
    "                res = 0\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(up + 1):\n",
    "                    print('i, d = ', i,  d)\n",
    "                    if first_zero and d == 0:\n",
    "                        res += solve(i + 1, cur_num, sum1, is_limit and d == up, first_zero and d == 0)\n",
    "                    elif d % 2 == 0:\n",
    "                        tmp = (cur_num + d * pow(10, len(s) - 1 - i)) % k\n",
    "                        res += solve(i + 1, tmp, sum1 + 1, is_limit and d == up, first_zero and d == 0)\n",
    "                    else:\n",
    "                        tmp = (cur_num + d * pow(10, len(s) - 1 - i)) % k\n",
    "                        res += solve(i + 1, tmp, sum1 - 1, is_limit and d == up, first_zero and d == 0)\n",
    "                return res\n",
    "            return solve(0, 0, 0, True, True)\n",
    "\n",
    "        min_res = 0\n",
    "        num11, num22 = 0, 0\n",
    "        for s_i in str(low):\n",
    "            if int(s_i) % 2 == 0:\n",
    "                num11 += 1\n",
    "            else:\n",
    "                num22 += 1\n",
    "        if num11 == num22 and low % k == 0:\n",
    "            min_res += 1\n",
    "        ans = f(str(high)) - f(str(low)) + min_res\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        dp = []\n",
    "        dp.append([\n",
    "            [[0]*k\n",
    "            for i in range(21)]\n",
    "            for j in range(10)\n",
    "        ])\n",
    "        for i in range(10):\n",
    "            dp[0][i][(1 if i %2 else -1)+10][i%k] += 1\n",
    "        \n",
    "        base = 1\n",
    "        for i in range(9):\n",
    "            base *= 10\n",
    "            tmp = [\n",
    "                [[0]*k\n",
    "                for l in range(21)]\n",
    "                for j in range(10)\n",
    "            ]\n",
    "            for j in range(10):\n",
    "                for k2 in range(21):\n",
    "                    for l in range(k):\n",
    "                        if not dp[i][j][k2][l]: continue\n",
    "                        # print(i, j, k2, l, dp[i][j][k2][l])\n",
    "                        for j2 in range(10):\n",
    "                            num = j2*base\n",
    "                            tmp[j2]\n",
    "                            tmp[j2][(1 if j2 %2 else -1)+k2]\n",
    "                            tmp[j2] \\\n",
    "                            [(1 if j2 %2 else -1)+k2] \\\n",
    "                            [(l+num)%k] += dp[i][j][k2][l]\n",
    "            dp.append(tmp)\n",
    "            \n",
    "        # print(dp)\n",
    "        \n",
    "        def getCount(num):\n",
    "            if num == 0:\n",
    "                return 0\n",
    "            t = num\n",
    "            # length = 0\n",
    "            base = 1\n",
    "            digits = []\n",
    "            while t:\n",
    "                digits.append(t%10)\n",
    "                # length += 1\n",
    "                t //= 10\n",
    "                base *= 10\n",
    "                \n",
    "            print(digits)\n",
    "            minus = 0\n",
    "            ret = 0\n",
    "            prefix = 0\n",
    "            for index, digit in list(enumerate(digits))[::-1]:\n",
    "                base //= 10\n",
    "                if index+1 ==len(digits):\n",
    "                        for i in range(1, digit):\n",
    "                            ret += dp[index][i][10][0]\n",
    "                        # ret += dp[index][0][9][0]\n",
    "                else:\n",
    "                    for i in range(0, digit):\n",
    "                        ret += dp[index][i][10-minus][(k-prefix%k)%k]\n",
    "\n",
    "                # print\n",
    "                minus += (1 if digit %2 else -1)\n",
    "                prefix += digit*base\n",
    "                print(index, digit, ret)\n",
    "            \n",
    "            for i in range(len(digits)-1):\n",
    "                for j in range(1, 10):\n",
    "                    ret += dp[i][j][10][0]\n",
    "\n",
    "            if prefix%k== 0 and minus==0:\n",
    "                return ret + 1\n",
    "            else:\n",
    "                return ret\n",
    "        \n",
    "        print(getCount(high), getCount(low-1))\n",
    "        return getCount(high) - getCount(low-1)\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(h: int) -> int:\n",
    "            high_str = str(h)\n",
    "            @cache\n",
    "            def dfs(index:int, val:int, even_odd_num_diff:int, reach_limit:bool, is_num_populated:bool) -> int:\n",
    "                if index == len(high_str):\n",
    "                    return int(val == 0 and is_num_populated and even_odd_num_diff == 0)\n",
    "            \n",
    "                ans = 0\n",
    "                if not is_num_populated:\n",
    "                    ans += dfs(index + 1, val, even_odd_num_diff, False, False)\n",
    "            \n",
    "                upper = int(high_str[index]) if reach_limit else 9\n",
    "                lower = 0 if is_num_populated else 1\n",
    "                for digit in range(lower, upper + 1):\n",
    "                    ### (val * (10 % k) % k + digit % k) % k\n",
    "                    ans += dfs(index + 1, (val * (10 % k) % k + digit % k) % k, even_odd_num_diff + (1 if digit % 2 else -1), digit == int(high_str[index]) and reach_limit, True)\n",
    "                return ans\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high: int)->int:\n",
    "            s = str(high)\n",
    "            @cache\n",
    "            def f(i: int,val: int,diff: int,is_num: bool,is_limit: bool)->int:\n",
    "                if i == len(s):\n",
    "                   return int(val==0 and diff==0)\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i+1,val,diff,False,False)\n",
    "                d0 = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(d0,up+1):\n",
    "                    res += f(i+1,(val*10+d)%k,diff+d%2*2-1,True,is_limit and d == up)\n",
    "                return res\n",
    "            return f(0,0,0,False,True)    \n",
    "        return calc(high)-calc(low-1)            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(num):\n",
    "            s = str(num)\n",
    "            @cache\n",
    "            def f(i, diff, mod, is_limit, is_num):\n",
    "                if i == len(s):\n",
    "                    if diff == 0 and mod == 0 and is_num:\n",
    "                        return 1\n",
    "                    return 0\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = f(i + 1, diff, mod, False, False)\n",
    "                mi = 0 if is_num else 1\n",
    "                ma = int(s[i]) if is_limit else 9\n",
    "                for j in range(mi, ma + 1):\n",
    "                    t = 1 if (j & 1) else -1\n",
    "                    res += f(i + 1, diff + t, (mod * 10 + j) % k, is_limit and j == ma, True)\n",
    "                return res\n",
    "            return f(0, 0, 0, True, False)\n",
    "        \n",
    "        return calc(high) - calc(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(n):\n",
    "            s = str(n) \n",
    "            @cache         \n",
    "            def dfs(i,rem,diff,is_num,is_limit):\n",
    "                if i == len(s):\n",
    "                    return int(is_num and rem == 0 and diff == 0)      \n",
    "                ans = 0\n",
    "                if not is_num:\n",
    "                    ans += dfs(i + 1,rem,diff,False,False)\n",
    "                d0 = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for j in range(d0,up + 1):\n",
    "                    ans += dfs(i + 1,(rem*10 + j) % k,diff + j%2*2 - 1,True,is_limit and j == up)\n",
    "                return ans\n",
    "            return dfs(0,0,0,False,True)\n",
    "        return calc(high) - calc(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\n",
    "        def calc(high):\n",
    "            high = list(map(int, [c for c in str(high)]))\n",
    "            n = len(high)\n",
    "            nonlocal k\n",
    "            @cache\n",
    "            def dfs(i, val, diff, isLimit, isNum):\n",
    "                if i == n:\n",
    "                    if val ==0 and diff == 0:\n",
    "                        return 1\n",
    "                    else:\n",
    "                        return 0\n",
    "                \n",
    "                res = 0\n",
    "                if not isNum:\n",
    "                   res += dfs(i+1, 0, 0, False, False) \n",
    "                \n",
    "                low = 0 if isNum else 1\n",
    "                up = high[i] if isLimit else 9\n",
    "\n",
    "                for d in range(low, up+1):\n",
    "                    res += dfs(i+1, (val*10 + d)%k, diff + (d%2)*2-1, isLimit and d == up, True)\n",
    "                return res\n",
    "\n",
    "            return dfs(0,0,0,True,False)\n",
    "        \n",
    "        a = calc(high)\n",
    "        b = calc(low-1)\n",
    "        #print(a,b)\n",
    "        return a - b\n",
    "    \n",
    "    \n",
    "    def numberOfBeautifulIntegers2(self, low: int, high: int, k: int) -> int:\n",
    "        \n",
    "        def check(x):\n",
    "            e = 0\n",
    "            o = 0\n",
    "            while x:\n",
    "                c = x % 10\n",
    "                if c % 2 == 0:\n",
    "                    e += 1\n",
    "                else:\n",
    "                    o += 1\n",
    "                \n",
    "                x = x // 10\n",
    "            return e ==o\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(low, high+1):\n",
    "            if i % k == 0 and check(i):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def cal(high):\n",
    "            s = str(high)\n",
    "            @cache\n",
    "            def dfs(i, val, diff, is_limit, is_num):\n",
    "                # is_limit: 0-i-1是否贴着上界\n",
    "                # is_num: 0-i-1是否是数字\n",
    "                # 递归终止条件\n",
    "                if i==len(s):\n",
    "                    if val==0 and diff==0 and is_num:\n",
    "                        return 1\n",
    "                    else:\n",
    "                        return 0\n",
    "                res = 0\n",
    "                # 前导0的情况\n",
    "                if not is_num: # 如果都是前导0，当前位置可以不填\n",
    "                    res += dfs(i+1, val, diff, False, False)\n",
    "                # 非前导0的情况\n",
    "                down = 1 if not is_num else 0 # 如果前面都是0，第i位只能从1开始，如果前面不是0，那么第i位可以从0开始\n",
    "                up = int(s[i]) if is_limit else 9 # 如果前面的数字达到上界，那么第i位最多是s[i]；如果没有达到上界，那么第i位最多是9\n",
    "                for d in range(down, up+1):\n",
    "                    res += dfs(i+1, (val*10+d) % k, diff + d%2*2-1, is_limit and d==up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return cal(high)-cal(low-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        str1=str(low)\n",
    "        # dp=[[[-1]*len(high) for _ in range(k)] for _ in range(len(high))]\n",
    "        def calc(n):\n",
    "            n=str(n)\n",
    "            @cache\n",
    "            def dfs(pos,islimit,isnum,cur_num,odd_num):\n",
    "                if pos>=len(n):\n",
    "                    if cur_num ==0 and odd_num==0:return 1\n",
    "                    return 0\n",
    "                # if dp[pos][cur_num][odd_num]!=-1:return dp[pos][cur_num][odd_num]\n",
    "                low=0 if isnum else 1\n",
    "                up=int(n[pos]) if islimit else 9\n",
    "                ans=0\n",
    "                if not isnum:\n",
    "                    ans+=dfs(pos+1,False,False,0,0)\n",
    "                for i in range(low,up+1):\n",
    "                    ans+=dfs(pos+1,islimit and i==up,True,(cur_num*10+i )% k,odd_num+(1 if i&1 else -1))\n",
    "                # dp[pos][cur_num][odd_num]=ans\n",
    "                return ans\n",
    "            return dfs(0,True,False,0,0)\n",
    "        return calc(high)-calc(low-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high):\n",
    "            s=str(high)\n",
    "            @cache\n",
    "            def dfs(i,val,diff,is_limit,is_num):\n",
    "                if i==len(s):\n",
    "                    return int(is_num and val==0 and diff==0)\n",
    "                res=0\n",
    "                if not is_num:\n",
    "                    res=dfs(i+1,val,diff,False,False)\n",
    "                d0=0 if is_num else 1\n",
    "                up=int(s[i]) if is_limit else 9\n",
    "                for d in range(d0,up+1):\n",
    "                    res+=dfs(i+1,(val*10+d)%k,diff+d%2*2-1,is_limit and d==up,True)\n",
    "                return res\n",
    "            return dfs(0,0,0,True,False)\n",
    "        return calc(high)-calc(low-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mods = [[0] * 21 for _ in range(10)]\n",
    "for i in range(10):\n",
    "    for k in range(1, 21):\n",
    "        mods[i][k] = (10 ** i) % k\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\n",
    "        def helper(s):\n",
    "            n = len(s)\n",
    "\n",
    "            @functools.lru_cache(None)\n",
    "            def dfs(idx, isLimit, isNum, isPre, mod):\n",
    "                if idx == n:\n",
    "                    return isPre and isNum == mod == 0 \n",
    "                res = 0 if isPre else dfs(idx + 1, False, isNum, isPre, mod)\n",
    "                low = 0 if isPre else 1\n",
    "                up = int(s[idx]) if isLimit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    res += dfs(idx + 1, isLimit and d == int(s[idx]), isNum + 2 * (d % 2) - 1, True, (mod + d * mods[n - 1 - idx][k]) % k)\n",
    "                return res\n",
    "\n",
    "            return dfs(0, True, 0, False, 0)\n",
    "\n",
    "        return helper(str(high)) - helper(str(low - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def clac(num: int) -> int:\n",
    "            s = str(num)\n",
    "\n",
    "            @cache\n",
    "            def dfs(i, diff, mod: int, limit, num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(num and diff == 0 and mod == 0)\n",
    "                res = 0\n",
    "                if not num:\n",
    "                    res += dfs(i + 1, 0, 0, False, False)\n",
    "                low, up = 1 if not num else 0, int(ord(s[i]) - ord('0')) if limit else 9\n",
    "                while low <= up:\n",
    "                    res += dfs(i + 1, diff + low % 2 * 2 - 1, (mod * 10 + low) % k,\n",
    "                               low == up and limit, True)\n",
    "                    low += 1\n",
    "                return res\n",
    "\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "\n",
    "        return clac(high) - clac(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high: int) -> int:\n",
    "            s = str(high)\n",
    "            @cache  # 记忆化搜索\n",
    "            def dfs(i: int, val: int, diff: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num and val == 0 and diff == 0)  # 找到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = dfs(i + 1, val, diff, False, False)\n",
    "                d0 = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 high 的一样，那么这一位至多填 s[i]（否则就超过 high 啦）\n",
    "                for d in range(d0, up + 1):  # 枚举要填入的数字 d\n",
    "                    res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit and d == up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high: int) -> int:\n",
    "            s = str(high)\n",
    "            @cache  # 记忆化搜索\n",
    "            def dfs(i: int, val: int, diff: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num and val == 0 and diff == 0)  # 找到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = dfs(i + 1, val, diff, False, False)\n",
    "                d0 = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 high 的一样，那么这一位至多填 s[i]（否则就超过 high 啦）\n",
    "                for d in range(d0, up + 1):  # 枚举要填入的数字 d\n",
    "                    res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit and d == up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high: int) -> int:\n",
    "            s = str(high)\n",
    "            @cache  # 记忆化搜索\n",
    "            def dfs(i: int, val: int, diff: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num and val == 0 and diff == 0)  # 找到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = dfs(i + 1, val, diff, False, False)\n",
    "                d0 = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 high 的一样，那么这一位至多填 s[i]（否则就超过 high 啦）\n",
    "                for d in range(d0, up + 1):  # 枚举要填入的数字 d\n",
    "                    res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit and d == up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high): \n",
    "            s =str(high) \n",
    "            n = len(s)\n",
    "            @cache\n",
    "            def dfs(i:int,mask:int,diff:int,limit:bool,isnum:bool):\n",
    "                if i ==n:\n",
    "                    return int(isnum and mask==0 and diff ==0)  \n",
    "                \n",
    "                res = 0\n",
    "\n",
    "                if not isnum:\n",
    "                    res =dfs(i+1,mask,diff,False,False)\n",
    "                \n",
    "                up = int(s[i]) if limit else 9\n",
    "\n",
    "                down = 0 if isnum else 1\n",
    "\n",
    "                for  d in range(down,up+1):\n",
    "                    res += dfs(i+1,(mask*10+d)%k,diff+d%2*2-1,limit and d==up,True)\n",
    "                return res\n",
    "            return dfs(0,0,0,True,False)\n",
    "        return calc(high)-calc(low-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dp(high, digit, residue, difference, isLimit, isTested):\n",
    "            res = 0\n",
    "            if digit == len(high):\n",
    "                return int(residue == 0 and difference == 0 and isTested)\n",
    "            if isTested == False:\n",
    "                res = dp(high, digit + 1, residue, difference, False, False)\n",
    "            down = 0 if isTested else 1\n",
    "            up = int(high[digit]) if isLimit else 9\n",
    "            for num in range(down, up + 1):\n",
    "                res += dp(high, digit + 1, (residue * 10 + num) % k, difference + 2 * (num % 2) - 1, isLimit and num == up, True)\n",
    "            return res\n",
    "        return dp(str(high), 0, 0, 0, True, False) - dp(str(low - 1), 0, 0, 0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://space.bilibili.com/206214\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high: int) -> int:\n",
    "            s = str(high)\n",
    "            @cache  # 记忆化搜索\n",
    "            def dfs(i: int, val: int, diff: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num and val == 0 and diff == 0)  # 找到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = dfs(i + 1, val, diff, False, False)\n",
    "                d0 = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 high 的一样，那么这一位至多填 s[i]（否则就超过 high 啦）\n",
    "                for d in range(d0, up + 1):  # 枚举要填入的数字 d\n",
    "                    res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit and d == up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        str1=str(low)\n",
    "        # dp=[[[-1]*len(high) for _ in range(k)] for _ in range(len(high))]\n",
    "        @cache\n",
    "        def dfs(pos,islimit,isnum,cur_num,odd_num,n):\n",
    "            if pos>=len(n):\n",
    "                if cur_num ==0 and odd_num==0:return 1\n",
    "                return 0\n",
    "            # if dp[pos][cur_num][odd_num]!=-1:return dp[pos][cur_num][odd_num]\n",
    "            low=0 if isnum else 1\n",
    "            up=int(n[pos]) if islimit else 9\n",
    "            ans=0\n",
    "            if not isnum:\n",
    "                ans+=dfs(pos+1,False,False,0,0,n)\n",
    "            for i in range(low,up+1):\n",
    "                ans+=dfs(pos+1,islimit and i==up,True,(cur_num*10+i )% k,odd_num+(1 if i&1 else -1),n)\n",
    "            # dp[pos][cur_num][odd_num]=ans\n",
    "            return ans\n",
    "        return dfs(0,True,False,0,0,str(high))-dfs(0,True,False,0,0,str(low-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\n",
    "        def helper(s):\n",
    "            n = len(s)\n",
    "\n",
    "            @functools.lru_cache(None)\n",
    "            def dfs(idx, isLimit, isNum, isPre, mod):\n",
    "                if idx == n:\n",
    "                    return isPre and isNum == mod == 0 \n",
    "                res = 0 if isPre else dfs(idx + 1, False, isNum, isPre, mod)\n",
    "                low = 0 if isPre else 1\n",
    "                up = int(s[idx]) if isLimit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    res += dfs(idx + 1, isLimit and d == int(s[idx]), isNum + 2 * (d % 2) - 1, True, (mod * 10 + d) % k)\n",
    "                return res\n",
    "\n",
    "            return dfs(0, True, 0, False, 0)\n",
    "\n",
    "        return helper(str(high)) - helper(str(low - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def findnum(odd,mod,num,tag,pre):\n",
    "            l=len(num)\n",
    "            if odd==0 and l==0 and mod==0:return 1\n",
    "            if l==0 or abs(odd)>l:\n",
    "                return 0\n",
    "            res=0\n",
    "            bd=int(num[0]) if tag else 9\n",
    "            for i in range(bd,-1,-1):\n",
    "                if i==0 and pre==False:res+=findnum(0,0,num[1:],False,False)\n",
    "                else: res+=findnum(odd+(1 if i&1 else -1),(mod*10+i)%k,num[1:],tag,pre|i>0)\n",
    "                tag=False\n",
    "            return res\n",
    "        return findnum(0,0,str(high),True,False)-findnum(0,0,str(low-1),True,False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def findnum(odd,mod,num,mx,pre):\n",
    "            l=len(num)\n",
    "            if odd==0 and l==0 and mod==0:return 1\n",
    "            if l==0 or abs(odd)>l:\n",
    "                return 0\n",
    "            res=0\n",
    "            bd=int(num[0]) if mx else 9\n",
    "            for i in range(bd,-1,-1):\n",
    "                if i==0 and pre==False:res+=findnum(0,0,num[1:],False,False)\n",
    "                else: res+=findnum(odd+(1 if i&1 else -1),(mod*10+i)%k,num[1:],mx,pre|i>0)\n",
    "                mx=False\n",
    "            return res\n",
    "        return findnum(0,0,str(high),True,False)-findnum(0,0,str(low-1),True,False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def f(i:int,limit:bool,num:bool,s:str,now:int,mod:int)->int:\n",
    "            if i==len(s):\n",
    "                if not num:return 0\n",
    "                return mod%k==0 and now==0\n",
    "            res=0\n",
    "            if not num:\n",
    "                res=f(i+1,False,False,s,0,0)\n",
    "            up=int(s[i]) if limit else 9\n",
    "            di=0\n",
    "            if not num:di=1\n",
    "            for d in range (di,up+1):\n",
    "                res+=f(i+1,limit and d==up,True,s,now+(1 if d%2==0 else -1),(d+mod*10)%k)\n",
    "            return res\n",
    "        \n",
    "\n",
    "\n",
    "        return f(0,True,False,str(high),0,0)-f(0,True,False,str(low-1),0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def findnum(odd,mod,num,mx,pre):\n",
    "            l=len(num)\n",
    "            if odd==0 and l==0 and mod==0:return 1\n",
    "            if l==0 or abs(odd)>l:\n",
    "                return 0\n",
    "            res=0\n",
    "            bd=int(num[0]) if mx else 9\n",
    "            for i in range(bd,-1,-1):\n",
    "                if i==0 and pre==False:res+=findnum(0,0,num[1:],False,False)\n",
    "                else: res+=findnum(odd+(1 if i&1 else -1),(mod*10+i)%k,num[1:],mx,pre|i>0)\n",
    "                mx=False\n",
    "            return res\n",
    "        return findnum(0,0,str(high),True,False)-findnum(0,0,str(low-1),True,False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(high: int) -> int:\n",
    "            s = str(high)\n",
    "            @cache  \n",
    "            def dfs(i: int, val: int, diff: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num and val == 0 and diff == 0)  \n",
    "                res = 0\n",
    "                if not is_num:  \n",
    "                    res = dfs(i + 1, val, diff, False, False)\n",
    "                d0 = 0 if is_num else 1  \n",
    "                up = int(s[i]) if is_limit else 9 \n",
    "                print(up)\n",
    "                for d in range(d0, up + 1):  \n",
    "                    res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit and d == up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        return self.cal(high, k) - self.cal(low-1, k)\n",
    "    \n",
    "    def cal(self, n: int, k: int) -> int:\n",
    "        \n",
    "        length = len(str(n))\n",
    "        s_n = str(n)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, l, r, remain, is_limit):\n",
    "            if i == length:\n",
    "                kkk = int(remain == 0 and l == r and l>0)\n",
    "                #if kkk:\n",
    "                    ##print(i, l, r, remain, is_limit)\n",
    "                return kkk\n",
    "            res = 0\n",
    "            if l == 0 and r == 0:\n",
    "                res += dfs(i+1, l, r, remain, False)\n",
    "            if l * 2 < length:\n",
    "                for v in range(0, 10, 2):\n",
    "                    if v == 0 and l == r == 0:\n",
    "                        continue\n",
    "                    if is_limit and v > int(s_n[i]):\n",
    "                        continue\n",
    "                    #print('\\t even', f'add {v=}', i, l, r, remain, is_limit)\n",
    "                    res += dfs(i+1, l+1, r, (remain * 10 + v) % k, is_limit and v==int(s_n[i]))\n",
    "            if r * 2 < length:\n",
    "                for v in range(1, 10, 2):\n",
    "                    if is_limit and v > int(s_n[i]):\n",
    "                        continue\n",
    "                    #print('\\t odd', f'add {v=}', i, l, r, remain, is_limit)\n",
    "                    res += dfs(i+1, l, r+1, (remain * 10 + v) % k, is_limit and v==int(s_n[i]))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0, 0, 0, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        n = max(len(str(low)), len(str(high)))\n",
    "        s1 = str(low-1)\n",
    "        s2 = str(high)\n",
    "            \n",
    "        @cache    \n",
    "        def f(i, is_num, is_limit, odd, r, s):\n",
    "            if i == len(s):\n",
    "                return int(is_num and odd == 0 and r == 0)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i+1, False, False, odd, r*10, s)\n",
    "            lo = 0 if is_num else 1    \n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for j in range(lo, up + 1):\n",
    "                res += f(i+1, True, j == up and is_limit, odd + (1 if j % 2 == 1 else -1), (r*10 + j) % k, s)\n",
    "                if r == 5 and j == 4:\n",
    "                    print(res)\n",
    "            return res    \n",
    "        return f(0, False, True, 0, 0, s2) - f(0, False, True, 0, 0, s1)\n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        ma = {}\n",
    "\n",
    "        def get(x, o, e, m, started):\n",
    "            if len(x) == 0:\n",
    "                if not started:\n",
    "                    return 0\n",
    "                if m == 0 and o == e:\n",
    "                    return 1\n",
    "                return 0\n",
    "            kk = (x, o, e, m, started)\n",
    "            if kk in ma:\n",
    "                return ma[kk]\n",
    "            h = x[0]\n",
    "            sz = len(x)\n",
    "            ans = 0\n",
    "            for i in range(int(h) + 1):\n",
    "                if not started and i == 0:\n",
    "                    xx = '9' * (sz - 1)\n",
    "                    ans += get(xx, o, e, m, False)\n",
    "                else:\n",
    "                    oo = o\n",
    "                    ee = e\n",
    "                    if i & 1:\n",
    "                        oo += 1\n",
    "                    else:\n",
    "                        ee += 1\n",
    "                    if i == int(h):\n",
    "                        xx = x[1:]\n",
    "                    else:\n",
    "                        xx = '9' * (sz - 1)\n",
    "                    ans += get(xx, oo, ee, (m * 10 + i) % k, True)\n",
    "            ma[kk] = ans\n",
    "            return ans\n",
    "\n",
    "        h = get(str(high), 0, 0, 0, False)\n",
    "        l = get(str(low - 1), 0, 0, 0, False) if low > 1 else 0\n",
    "        print(ma)\n",
    "        return h - l\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    x = Solution()\n",
    "    ans = x.numberOfBeautifulIntegers(1, 10, 1)\n",
    "    print(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\n",
    "        def f(s):\n",
    "            n = len(s)\n",
    "\n",
    "            @cache\n",
    "            def f(i, p, even, odd, is_limit):\n",
    "                if i == n:\n",
    "                    return int(even+odd>0 and even == odd and p == 0)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                down = 0 if even+odd else 1\n",
    "                ans = 0\n",
    "                if not even+odd:\n",
    "                    ans += f(i + 1, 0, 0, 0, False)\n",
    "                for j in range(down, up + 1):\n",
    "                    ans += f(i + 1, (p * 10 + j) % k, even + (not j & 1), odd + (j & 1), is_limit and j == up)\n",
    "\n",
    "                return ans\n",
    "\n",
    "            return f(0, 0, 0, 0, True)\n",
    "\n",
    "        return f(str(high)) - f(str(low - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(n):\n",
    "            s = str(n)\n",
    "            m = len(s)\n",
    "\n",
    "            @cache\n",
    "            def f(i: int, even: int, odd: int, mod: int, is_num: bool, is_limit: bool) -> int:\n",
    "                if i == m:\n",
    "                    return even == odd and mod == 0 and is_num\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res += f(i + 1, 0, 0, 0, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                high = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, high + 1):\n",
    "                    res += f(i + 1, even + (d % 2 == 0), odd + (d % 2 == 1), (mod * 10 + d) % k, True, is_limit and d == high)\n",
    "                return res\n",
    "            return f(0, 0, 0, 0, False, True)\n",
    "            \n",
    "        return calc(high) - calc(low - 1)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def cal(s:str):\n",
    "            @cache\n",
    "            def dfs(i:int, is_limit:bool, is_num:bool,sub:int,odd:int,even:int)->int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num) and sub==0 and odd==even\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i+1,0,0,0,False,False) \n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                low = 0 if is_num else 1\n",
    "                for d in range(low,up+1):\n",
    "                    oo = odd + (d%2==1)\n",
    "                    ee = even + (d%2==0)\n",
    "                    res += dfs(i+1,is_limit and d==up,True,(sub*10+d)%k,oo,ee) \n",
    "                return res\n",
    "            return dfs(0,True,False,0,0,0)\n",
    "        return cal(str(high))-cal(str(low-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(x: str):\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, mask1: int, mask2: int, is_limit: bool, is_num: bool, s: int) -> int:\n",
    "                if i == len(x):\n",
    "                    return int(is_num and mask1 == mask2 and s % k == 0)  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, 0, 0, False, False, 0)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(x[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    \n",
    "                    res += f(i + 1, mask1 + int(d % 2== 0), mask2 +int(d % 2 == 1), is_limit and d == up, True, (s * 10 + d) % k)\n",
    "                return res\n",
    "            return f(0, 0, 0, True, False, 0)\n",
    "        return calc(str(high)) - calc(str(int(low) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        \n",
    "        def help(x):\n",
    "            n = len(x)\n",
    "            @cache\n",
    "            def dfs(i, is_up, is_num, even, odd, v):\n",
    "                if i == n:\n",
    "                    if is_num and even == odd and v == 0:\n",
    "                        return 1\n",
    "                    return 0\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res += dfs(i + 1, False, False, even, odd, v)\n",
    "                \n",
    "                low = 1 if not is_num else 0\n",
    "                up = int(x[i]) if is_up else 9\n",
    "                \n",
    "                for d in range(low, up + 1):\n",
    "                    e = o = 0\n",
    "                    if d % 2 == 0:\n",
    "                        e = 1\n",
    "                    else:\n",
    "                        o = 1\n",
    "                    res += dfs(i + 1, is_up and d == up, True, even + e, odd + o, ((v * (10 % k)) % k + d % k) % k)\n",
    "                return res\n",
    "            return dfs(0, True, False, 0,0,0)\n",
    "        \n",
    "        def check(x):\n",
    "            even = odd = 0\n",
    "            for i in range(len(x)):\n",
    "                if int(x[i]) % 2 == 0:\n",
    "                    even += 1\n",
    "                else:\n",
    "                    odd += 1\n",
    "            return 0 if odd != even or int(x) % k != 0 else 1\n",
    "        \n",
    "        return help(str(high)) - help(str(low)) + (1 if check(str(low)) else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def cal(s:str,k):\n",
    "            @cache\n",
    "            def dfs(i:int, is_limit:bool, is_num:bool,sub:int,odd:int,even:int)->int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num) and sub==0 and odd==even\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i+1,0,0,0,False,False) \n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                low = 0 if is_num else 1\n",
    "                for d in range(low,up+1):\n",
    "                    oo = odd + (d%2==1)\n",
    "                    ee = even + (d%2==0)\n",
    "                    res += dfs(i+1,is_limit and d==up,True,(sub*10+d)%k,oo,ee) \n",
    "                return res\n",
    "            return dfs(0,True,False,0,0,0)\n",
    "        return cal(str(high),k)-cal(str(low-1),k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s):\n",
    "            n = len(s)\n",
    "            @cache\n",
    "            def dfs(i, p, even, odd, limit, is_num):\n",
    "                if(i == n):\n",
    "                    return (int)(even == odd and is_num and p == 0)\n",
    "                up = int(s[i]) if limit else 9\n",
    "                down = 0 if is_num else 1\n",
    "                ans = 0\n",
    "\n",
    "                if not is_num:\n",
    "                    ans += dfs(i+1, 0, 0, 0, False, False)\n",
    "\n",
    "                for j in range(down, up+1):\n",
    "                    ans += dfs(i+1, (p*10+j)%k, even + (j&1), odd+((j&1) == 0), limit and (j == up), True)\n",
    "                    \n",
    "                return ans;\n",
    "            return dfs(0, 0, 0, 0, True, False)\n",
    "        \n",
    "        return f(str(high)) - f(str(low-1))\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        # from functools import cache\n",
    "        def solve(num):\n",
    "            @cache\n",
    "            def dfs(i,limit,isnum,odd,even,presum):\n",
    "                if i==length:\n",
    "                    return 1 if odd==even and presum%k==0 else 0\n",
    "                res=0\n",
    "                if not isnum:\n",
    "                    res+=dfs(i+1,False,False,odd,even,presum)\n",
    "                up,low=int(n[i]) if limit else 9,0 if isnum else 1\n",
    "                for d in range(low,up+1):\n",
    "                    res+=dfs(i+1,d==up and limit,True,odd+(1 if d%2 else 0),even+(1 if d%2==0 else 0),(10*presum+d)%k)\n",
    "                return res\n",
    "            n=str(num)\n",
    "            length=len(n)\n",
    "            return dfs(0,True,False,0,0,0)\n",
    "        # print(solve(high))\n",
    "        # print(solve((low-1)))\n",
    "        return solve(high)-solve(low-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s):\n",
    "            n = len(s)\n",
    "            \n",
    "            @cache\n",
    "            def dfs(i,p,ev,od,is_limit,is_num):\n",
    "                if i == n:\n",
    "                    return int(is_num and ev==od and p==0)\n",
    "                up = int(s[i]) if is_limit else 9 \n",
    "                down = 0 if is_num else 1 \n",
    "                ans = 0 \n",
    "                if not is_num:\n",
    "                    ans += dfs(i+1,0,0,0,False,False)\n",
    "                for j in range(down,up+1):\n",
    "                    ans += dfs(i+1,(p*10+j)%k,ev+(j&1),od+((j&1)==0),is_limit and j == up,True)                \n",
    "                \n",
    "                return ans\n",
    "            \n",
    "            return dfs(0,0,0,0,True,False)\n",
    "            \n",
    "        return f(str(high)) - f(str(low-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "            \n",
    "        def inner(s:str) -> int:\n",
    "            @cache\n",
    "            def f(i:int,k_divide:int,odd_num:int,even_num:int,isLimit:bool,isNum:bool):\n",
    "                if i==len(s):return int(isNum and even_num==odd_num and k_divide==0)\n",
    "                res=0\n",
    "                if not isNum:res=f(i+1,k_divide,odd_num,even_num,False,False)\n",
    "\n",
    "                low= 0 if isNum else 1\n",
    "                up=int(s[i]) if isLimit else 9\n",
    "\n",
    "                for d in range(low,up+1):\n",
    "                    if d%2==1:res+=f(i+1,(k_divide * 10 + d) % k,odd_num+1,even_num,isLimit and d==up,True)\n",
    "                    else:res+=f(i+1,(k_divide * 10 + d) % k,odd_num,even_num+1,isLimit and d==up,True)\n",
    "                return res\n",
    "\n",
    "            return f(0,0,0,0,True,False)\n",
    "\n",
    "        return inner(str(high))-inner(str(low-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def f(s):\n",
    "            n=len(s)\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int,j,o,is_limit: bool, is_num: bool,sum) -> int:\n",
    "                if i == n:\n",
    "                    return int(is_num) and sum%k==0 and j==o\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, j,o,False, False,sum)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "                for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                    if d%2:\n",
    "                        res += f(i + 1,j+1,o, is_limit and d == up, True,(sum+d*pow(10,n-i-1))%k)\n",
    "                    else:\n",
    "                        res += f(i + 1, j,o+1, is_limit and d == up, True,(sum+d*pow(10,n-i-1))%k)\n",
    "                return res\n",
    "            return f(0,0,0,True, False,0)\n",
    "        ans = f(str(high)) - f(str(low-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n, k):\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        def dfs(index, is_limit, even, odd, mode, valid):\n",
    "            if index == len(s):\n",
    "                return valid and even == odd and mode == 0\n",
    "\n",
    "            ans = 0\n",
    "            end = int(s[index]) if is_limit else 9\n",
    "            base = 10 ** (len(s) - index - 1)\n",
    "            for number in range(0, end + 1):\n",
    "                new_odd = odd + int(number % 2 == 1)\n",
    "                new_valid = valid or number != 0\n",
    "                new_mode = (base * number + mode) % k\n",
    "                new_even = even + (0 if not new_valid else int(number % 2 == 0))\n",
    "                ans += dfs(index + 1, is_limit and number == end, new_even, new_odd, new_mode, new_valid)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, True, 0, 0, 0, False)\n",
    "    \n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        r1 = self.countDigitOne(low - 1, k)\n",
    "        r2 = self.countDigitOne(high, k)\n",
    "        return r2 - r1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "\n",
    "        def f(num: int):  # 数字 <= num 满足条件的所有数字\n",
    "            s = str(num)\n",
    "            @cache\n",
    "            def digitDp(i: int, remain: int, n_odds, n_even, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return 1 if is_num and remain == 0 and n_even == n_odds else 0\n",
    "                ans = 0\n",
    "                if not is_num:\n",
    "                    ans = digitDp(i + 1, 0, 0, 0, False, False)\n",
    "                upper = int(s[i]) if is_limit else 9  # 判断当前位是否受约束\n",
    "                lower = 0 if is_num else 1\n",
    "                for j in range(lower, upper + 1):\n",
    "                    if j & 1:\n",
    "                        ans += digitDp(i + 1, (remain * 10 + j) % k, n_odds + 1, n_even, is_limit and j == upper, True)\n",
    "                    else:\n",
    "                        ans += digitDp(i + 1, (remain * 10 + j) % k, n_odds, n_even + 1, is_limit and j == upper, True)\n",
    "                return ans\n",
    "            return digitDp(0, 0, 0, 0, True, False)\n",
    "\n",
    "        # print(f(47))\n",
    "        # print(f(100))\n",
    "        return f(high) - f(low - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        def calc(num):\n",
    "            s = str(num)\n",
    "            @cache\n",
    "            def dfs(pos:int, even:int, odd:int, sub:int, limit:bool, is_num:bool):\n",
    "                res = 0\n",
    "                if pos == len(s):\n",
    "                    return int(is_num and sub == 0 and even == odd)\n",
    "                if not is_num:\n",
    "                    res += dfs(pos + 1, even, odd, sub, False, False)\n",
    "                up = int(s[pos]) if limit else 9\n",
    "                low = 0 if is_num else 1\n",
    "                for i in range(low, up + 1):\n",
    "                    od =  odd + (i % 2 == 1)\n",
    "                    ev =  even + (i % 2 == 0)\n",
    "                    res += dfs(pos + 1, ev, od, (sub * 10 + i) % k, limit and (i == up), True)\n",
    "                return res\n",
    "            return dfs(0, 0, 0, 0, True, False)\n",
    "        return calc(high) - calc(low - 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs_high(i, odd_num, even_num, is_limit, is_num, m):\n",
    "            if(i == len(high)):\n",
    "                return m==0 and odd_num==even_num\n",
    "            res = 0\n",
    "            if(not is_num):\n",
    "                res = dfs_high(i+1, odd_num, even_num, False, False, m)\n",
    "            up = int(high[i]) if is_limit else 9\n",
    "            for d in range(1-int(is_num), up+1):\n",
    "                res += dfs_high(i+1, odd_num+d%2, even_num+(d%2!=1), is_limit and d==up, True, (m+d*10**(len(high)-i-1)) % k)\n",
    "            return res\n",
    "        \n",
    "        @cache\n",
    "        def dfs_low(i, odd_num, even_num, is_limit, is_num, m):\n",
    "            if(i == len(low)):\n",
    "                return m==0 and odd_num==even_num\n",
    "            res = 0\n",
    "            if(not is_num):\n",
    "                res = dfs_low(i+1, odd_num, even_num, False, False, m)\n",
    "            up = int(low[i]) if is_limit else 9\n",
    "            for d in range(1-int(is_num), up+1):\n",
    "                res += dfs_low(i+1, odd_num+d%2, even_num+(d%2!=1), is_limit and d==up, True, (m+d*10**(len(low)-i-1)) % k)\n",
    "            return res\n",
    "        high = str(high)\n",
    "        low = str(low-1)\n",
    "        return dfs_high(0, 0, 0, True, False, 0)-dfs_low(0, 0, 0, True, False, 0)\n",
    "            \n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
